/*
 * com.future CO.,ltd.
 */

package com.future;

/**
 * （2021阿里笔试原题）
 * 如果一个节点X，它左树结构和右树结构完全一样，那么我们说以X为头的子树是相等子树
 * 给定一棵二叉树的头节点head，返回head整棵树上有多少棵相等子树
 * 注意：不是对称树，两颗数相等，值也相等，相对位置也相等
 */
public class LeftRightSameTreeNumber {


    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(2);

        head.left.left = new Node(3);
        head.left.right = new Node(4);
        head.right.left = new Node(3);
        head.right.right = new Node(4);
        int a = getSameTreeNums(head);
        System.out.println(a);
        int a2 = getSameTreeNums_hash(head);
        System.out.println(a2);
    }

    private static int getSameTreeNums(Node head) {
        if (head == null) {
            return 0;
        }
        return process(head);
    }

    private static int process(Node head) {
        if (head == null) {
            return 0;
        }
        int n1 = process(head.left);
        int n2 = process(head.right);
        int n3 = isSame(head.left, head.right) ? 1 : 0;
        return n1 + n2 + n3;
    }

    private static boolean isSame(Node left, Node right) {
        /**
         * 相同为0，否则为1
         */
        if (left == null ^ right == null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }
        return left.value == right.value && isSame(left.left, right.left) && isSame(left.right, right.right);
    }


    /**
     * 用hash算法，把节点换成对象，然后转成hash字符串
     *
     * @param head
     * @return
     */
    private static int getSameTreeNums_hash(Node head) {
        if (head == null) {
            return 0;
        }
        Info info = process_hash(head);
        return info.ans;
    }

    private static Info process_hash(Node head) {
        if (head == null) {
            return new Info(0, "#");
        }
        Info left = process_hash(head.left);
        Info right = process_hash(head.right);
        String hashCode = MyHash.generatorHashCode(head.value + left.str + right.str);
        int ans = left.ans + right.ans + (left.str.equals(right.str) ? 1 : 0);
        return new Info(ans, hashCode);
    }


    private static class Info {
        public int ans;
        public String str;

        public Info(int ans, String str) {
            this.ans = ans;
            this.str = str;
        }

        @Override
        public String toString() {
            return "Info{" +
                    "ans=" + ans +
                    ", str='" + str + '\'' +
                    '}';
        }
    }
}
